#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::swap;
using std::vector;

/* // 快排
int partition(vector<int>& v, int left, int right)
{
    int pivot = v[right]; // 基准点

    int idx1;
    int idx2;
    idx1 = idx2 = left;
    for(idx2;idx2 < right;++ idx2)
    {
        if(v[idx2] <= pivot)
        {
            swap(v[idx1 ++],v[idx2]);
        }
    }
    swap(v[idx1],v[right]);
    return idx1;
}

vector<int> quickSort(vector<int> &v, int left, int right)
{
    if (left < right)
    {
        int middleIdx = partition(v, left, right);
        quickSort(v, 0, middleIdx - 1); // 排左边的
        quickSort(v, middleIdx + 1, right); // 排右边的
    }
    return v;
} */

int partition1(vector<int> &v,int left,int right)
{
    int pivot = v[right];
    int slow,fast;
    slow = fast = left;
    for(fast;fast < right;++ fast)
    {
        if(v[fast] >= pivot)
        {
            continue;
        }

        swap(v[slow ++],v[fast]);
    }

    swap(v[slow],v[right]);
    return slow;
}

void quickSort1(vector<int>& v,int left,int right)
{
    while (left < right)
    {
        int mid = partition1(v,left,right);
        quickSort1(v,0,mid- 1); // 排左边
        quickSort1(v,mid + 1,right); // 排右边
    }
    
}

int main(int argc, char const *argv[])
{
    vector<int> v({5, 2, 6, 67, 7, 4, 3, 6, 9, 44, 32});

    quickSort1(v, 0, v.size() - 1);
    for (auto &num : v)
    {
        cout << num << " ";
    }
    cout << "\n";
    getchar();
    return 0;
}
